package leetcode.editor.cn.q1_300.q50;

import leetcode.editor.cn.util.list.singly.ListNode;
import leetcode.editor.cn.util.list.singly.ListUtil;

/**
 * @author qidi
 * @date 2021-12-23 11:35:15
 */
class Q0086_PartitionList {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public ListNode partition(ListNode head, int x) {
            if (head == null || head.next == null) return head;

            ListNode h = null;
            ListNode xleft = null;
            ListNode xright = null;
            ListNode xh = null;

            ListNode node = head;

            while (node != null) {
                ListNode cur = node;
                if (node.val < x) {
                    if (xleft == null) {
                        h = node;
                        xleft = node;
                    } else{
                        xleft.next = node;
                        xleft = xleft.next;
                    }
                } else {
                    if (xright == null) {
                        xh = node;
                        xright = node;
                    } else{
                        xright.next = node;
                        xright = xright.next;
                    }
                }
                node = node.next;
                cur.next = null;
            }

            if (xleft == null) return xh;

            xleft.next = xh;

            return h;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0086_PartitionList().new Solution();
        ListUtil util = ListUtil.getInstance();
        solution.partition(util.generateFromArray(new int[]{1, 2}), 0);
        solution.partition(util.generateFromArray(new int[]{1, 4, 3, 2, 5, 2}), 3);
    }
}